For the third generation partnership project (hereinafter referred as the 3GPP) wideband code division multiple access (hereinafter referred as W-CDMA) system, the cell search process employed by a cellular phone has to execute a series of detections and testing procedures of synchronization codes in order to synchronize the cellular phone with its best base station. In general, the cell search algorithm of the 3GPP W-CDMA is divided into three ordered steps: 1) slot synchronization, 2) frame synchronization and code-group identification, and 3) scrambling-code determination. The first step involves using a primary synchronization code (hereinafter referred as PSC) to achieve slot synchronization. The second step involves using both the secondary synchronization codes (SSCs) and the Comma-Free Reed-Solomon (hereinafter referred as CFRS) codes to achieve frame synchronization and code-group identification. The third step involves using all the possible scrambling codes of the identified code group to execute a de-scrambling procedure for scrambling-code determination. Before achieving the synchronization, the cellular phone cannot begin to decode various channel messages broadcasted by the base station or measure various channel effects.
In this invention, we are concerned with the second step of the synchronization procedure, which involves decoding the CFRS code so as to determine the frame boundary and code group. The CFRS code is a Comma-Free code and Reed-Solomon code and thus it has the features of both. The Comma-Free code has a feature that no new Comma-Free codeword can be created by combining any two Comma-Free codewords. It is capable of being used for both error detection and synchronization simultaneously. The synchronization capability of a Comma-Free code is used by 3GPP W-CDMA to achieve frame synchronization. Generally, a Comma-Free code decoding circuit is composed of simple correlators. However, in 3GPP W-CDMA, the Comma-Free code is transmitted intermittently as opposed to the continual transmission used in other applications. Therefore, an ordinary Comma-Free code decoder is not applicable to the synchronization procedure of the 3GPP W-CDMA.
The CFRS code is a (15, 3) Reed-Solomon (hereinafter referred as RS) code with a powerful error correction capability that is essential to 3GPP W-CDMA. The design of a RS decoder has been discussed in detail in many articles, and the most widely used decoding method can be described as having four steps: 1) syndrome calculation of the received codeword, 2) error locator polynomial and error evaluator computations, 3) error location calculation, and 4) error value calculation. However, in 3GPP W-CDMA, the set of CFRS codes is composed of 64 special RS codes and thus an ordinary RS decoder is unsuitable.
3GPP W-CDMA uses 64 CFRS codes to represent 64 code groups. Each codeword consists of 15 symbols. Every code group includes eight scrambling codes. Every base station treats one of the eight scrambling codes of the code group to which it belongs as its scrambling code for differentiating itself from the other stations. To be connected through a certain base station, a cellular phone has to achieve scrambling code synchronization with the base station first. As described above, the synchronization process has to include a decoding procedure of a CFRS code for frame boundary detection and code-group determination.
The symbols of the CFRS code are chosen from the elements of Galois Field (GF) (16). Among the 16 secondary synchronization codes transmitted via a secondary synchronization channel, an nth cyclic-shift synchronization code represents that the nth code symbok, an element of GF (16), is regarded as the first code symbol. Symbols are selected to form 64 CFRS codes to represent 64 code groups. To transmit the CFRS codes, a base station sends identical codes in each frame. However, prior to frame synchronization, the assumed initial position for the receipt of CFRS codes is not necessarily occupied by the first code symbol, but can be occupied by any one of the 15 code symbols. Since the same CFRS code is transmitted in each frame, it is possible to receive 15 code symbols continuously even before a frame boundary is determined. The consecutive received 15 code symbols correspond to a cyclic-shift version of a CFRS codeword. The aim of decoding is to identify the received codeword as one of the 64 CFRS codes in order to determine the code group, and to detect the cyclic-shift amount so as to determine the frame boundary.
According to the above description, there are 64 CFRS codes and 15 cyclic-shift versions of each codeword. Thus there can be a total of 960 (64×15) versions of cyclic-shift codeword. The evaluation of these 960 cyclic-shift hypotheses requires a lot of complicated calculations, and more importantly, timely accomplishment of these calculations in order to avoid delay in the synchronization procedure that would cause more serious problems. Hence, decoding speed has a direct impact on real-time synchronization. A “fast” CFRS decoder is an indispensable component for the cell search algorithm.
The decoding methods discussed in the existing literature regarding cell search algorithms merely involve direct comparison of these 960 versions, thus there is no optimal decoding method, nor is there any optimal architecture for hardware implementation. Therefore, it is a good idea in implementing the direct decoding method based on the 960 versions to develop decoding hardware architecture that works optimally, as well as to put forward a decoding method that is optimal.